#include <iostream>
#include <vector>

namespace A {

	template<class T>
	struct less
	{
		/*bool operator < (T& left, T& right)
		{
			return left < right;
		}*/
		bool operator () (T& left, T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		/*bool operator > (T& right)
		{
			return left > right;
		}*/

		bool operator () (T& left, T& right)
		{
			return left > right;
		}
	};


	template<class T, class con = std::vector<T>, class com = less<T>>
	class priority_queue
	{
	private:
		//T _value;
		con _c;
	private:
		com compare;//显示的创建一个函数对象
		void Adjustup(int child)
		{
			int parent = ((child - 1) >> 2);
			while (parent >= 0)
			{
				//if (_c[parent] < _c[child] && com(_c[child], _c[child + 1])]) child++;
				//向上调整不需要判断这个，你插入位置的前一个，本来就小于原父节点
				if (compare(_c[parent], _c[child]))
				{
					std::swap(_c[parent], _c[child]);
					child = parent;
					parent = (child - 1) >> 2;
				}
				else
				{
					break;
				}

			}
		}

		void Adjustdown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _c.size())
			{
				if (child + 1 < _c.size() && com(_c[child], _c[child + 1])) ++child;
				if (compare(_c[parent], _c[child]))
				{
					std::swap(_c[parent], _c[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}


	public:
		priority_queue()//构造空的
			:_c()
		{}
		

		/*priority_queue(vector<T> c)
		{}*/
		template <class Iterator>
		priority_queue(Iterator first, Iterator last)
			: _c(first, last)
		{
			int n = _c.size();
			int parent = ((n - 2) >> 1);
			for (; parent >= 0; --parent)
			{
				Adjustdown(parent);
			}
			
		}

		void push(const T& value)
		{
			_c.push_back(value);
			Adjustup(_c.size() - 1);

		}

		bool empty()
		{
			return  _c.empty();
		}

		void pop()
		{
			if (!empty())
			{
				//std::swap(_c[0], _c[_c.size() - 1]);
				std::swap(_c.front(), _c.back());
				_c.pop_back();
				Adjustdown(0);
			}			
		}

		size_t size() const
		{
			return _c.size();
		}

		const T& top()const//堆顶元素不允许外部修改，会破坏堆的特性
		{
			return _c.front();
		}
	};

}

int main()
{
	A::priority_queue<int, std::vector<int>, A::greater<int>> q1;
	q1.push(5);
	q1.push(1);
	q1.push(4);
	q1.push(2);
	q1.push(3);
	q1.push(6);
	std::cout << q1.top() << std::endl;

	return 0;
}